﻿// 3706. 不连续1的子串.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;

/*
https://www.acwing.com/problem/content/3709/


请计算长度为 N且不含连续 1的 01串的个数。

例如，当 N=3时，答案为 5
，因为长度为 3且不含连续 1的 01串一共 5个：000,001,010,100,101。

输入格式
一个整数 N。

输出格式
一个整数，表示结果。

数据范围
1≤N≤20
输入样例：
3
输出样例：
5
*/


string str;
int ans = 0;
void dfs(int x) {
	if (x == 0) {
		ans++; return;
	}

	if (str.empty() || str.back() == '0') {
		str.push_back('1');
		dfs(x-1);
		str.pop_back();
	}

	str.push_back('0');
	dfs(x - 1);
	str.pop_back();
}

int main()
{
	int n; cin >> n;

	dfs(n);

	cout << ans << endl;
	return 0;
}

